1. Technical Field of the Invention
The present invention generally relates to wavelength division multiplex ring networks. More particularly, and not by way of any limitation, the present invention is directed to a system and method for dynamically assigning wavelengths in such networks.
2. Description of Related Art
WDM rings, including circuit-based rings and packet rings, such as WDM Resilient Packet Rings (“RPRs”) and WDM Gigabit Ethernet rings, are designed primarily for implementing metropolitan area networks (“MANs”). FIG. 1 is an example ring network 100 consisting of five nodes, respectively designated A-E, connected in a ring. Each node A-E is connected to its adjacent nodes via at least one link. Information is carried in one and only one direction on a ring, either clockwise or counter-clockwise.
A WDM ring is a ring with multiple wavelengths. Some wavelengths are assigned to traffic flows, while others are empty. The wavelengths assigned to flows carry traffic for one or more traffic classes (e.g., Gold, Silver, Best Effort) on each wavelength. Each time a new flow is admitted to the ring, a decision must be made as to on which wavelength the flow is to be sent. This choice directly affects the number of Optical/Electrical (“O/E”) and Electrical/Optical (“E/O”) interfaces that are to be included at each node, as well as the Quality of Service (“QoS”) of the existing flows. As used herein, QoS is synonymous with performance.
There are four types of wavelengths on which a new flow may be sent. First, a new flow may be sent on a new wavelength not assigned anywhere on the ring. Such wavelengths are designated “unused” wavelengths. Alternatively, a new flow may be sent on an existing wavelength that overlaps with the path for the new flow and still has available bandwidth. Such wavelengths are designated “grooming” wavelengths. Still further, a new flow may be sent on an existing wavelength that has been used in some other section of the ring, but will not overlap with the path for the new flow. Such wavelengths are designated “space-reusable” wavelengths. Finally, the new flow may be sent on an existing wavelength that has been used in some other section of the ring and will overlap with the path for the new flow. Such wavelengths are designated “grooming+space-reusable” wavelengths.
Each time a new wavelength is added at a node, an EO interface is required. Each time a new wavelength is dropped at a node, an OE interface is required. In contrast, if an existing wavelength is reused to carry new traffic in addition to the existing traffic it is carrying, no new OE or EO interfaces are required to be added. Use of existing wavelengths to transport new flows is likely to yield more optimal solutions; that is, selection of wavelengths with fewer OE/EO interfaces, which translates to lower costs.
It is therefore desirable to assign a wavelength to a new flow such that it results in the addition of a minimum number of OE/EO interfaces. A constraint on this goal is that the wavelength assignment of existing flows must not be changed to avoid rerouting of existing traffic flows. QoS issues may also be considered in identifying the optimal wavelength to which to assign a new flow. For example, the optimal wavelength may also be the one that best preserves the QoS of existing flows and maximizes the QoS for the new flow.
The term “dynamic” in “dynamic wavelength assignment” refers to the fact that optimal wavelengths are determined based on information about remaining available resources (e.g., wavelengths, OEs/EOs, bandwidth). Resources allocated to existing flows are not considered part of the optimization problem. In contrast, “static” solutions require that the information about all of the flows that will be added to the network be known before the optimization is performed.
Previously, a “default” method of assigning wavelengths to flows in WDM rings has been to perform an extensive search over all of the wavelengths and take the wavelength that best minimizes the number of OE/EO interfaces added. This method is deficient in that it is computationally intensive, particularly in rings with a large number of nodes and wavelengths. Two other default methods are referred to as “first-fit” and “best-fit”; however, neither first-fit nor best-fit consider minimization of OE/EO interfaces in the optimization.
Many of the remaining prior art solutions are restricted to static wavelength assignment methods. The primary disadvantage of static wavelength assignment methods is that, by definition, they provide static solutions; i.e., the best wavelength is determined a priori before admitting any new flow. This requires that the traffic matrix containing information for all possible flows (e.g., source, destination, traffic class, and available bandwidth) be known in advance. Clearly, this information may not always be available. Further, the addition of a new flow not already considered in the traffic matrix requires the redoing of the complete optimization with the new traffic flow; hence, optimal wavelengths cannot be computed in real time.
Additional deficiencies inherent in static solutions is that existing flows may have to be rerouted based on the results of the new optimization, which may not always be acceptable. Additionally, such solutions are computationally expensive because they require redoing the complete optimization each time.
In contrast to static solutions discussed above, a dynamic wavelength assignment algorithm would compute optimal wavelengths based on remaining resources and therefore would not require rerouting of existing traffic and resources. In particular, O. Gerstel, G. Sasaki, S. Kutten, R. Ramaswami, “Worst-Case Analysis of Dynamic Wavelength Allocation in Optical Networks,” IEEE/ACM Transactions on Networking, Volume 7, No. 6, December 1999 (hereinafter referred to as “Worst-Case Analysis”), discloses the worst case bounds for dynamic wavelength assignment in a WDM ring. However, “Worst-Case Analysis” provides no heuristics for dynamic wavelength assignment in WDM rings; moreover, it describes only mathematical bounds and does not provide an algorithm for dynamic wavelength assignment.
All other known prior art “dynamic” solutions relate to dynamic wavelength assignment in hubs and do not address WDM rings. Moreover, no known prior art solution considers the QoS of the existing flows and net traffic flows in the optimization process.